◀ Prev · Parts · Full · Next ▶

In each execution of the outer loop, the algorithm repeats the inner loop until only 2 nodes remain, the corresponding cut is obtained. The run time of one execution is O ( n ) {\displaystyle O(n)} , and n denotes the number of vertices. After m times executions of the outer loop, we output the minimum cut among all the results. The figure 2 gives an example of one execution of the algorithm. After execution, we get a cut of size 3.

Lemma 1—Let k be the min cut size, and let C = {e1, e2, ..., ek} be the min cut. If, during iteration i, no edge e ∈ C is selected for contraction, then Ci = C.

Proof

If G is not connected, then G can be partitioned into L and R without any edge between them. So the min cut in a disconnected graph is 0. Now, assume G is connected. Let V=L∪R be the partition of V induced by C : C = { {u,v} ∈ E : u ∈ L,v ∈ R} (well-defined since G is connected). Consider an edge {u,v} of C. Initially, u,v are distinct vertices. As long as we pick an edge ⁠ f ≠ ≠ e {\displaystyle f\neq e} ⁠, u and v do not get merged. Thus, at the end of the algorithm, we have two compound nodes covering the entire graph, one consisting of the vertices of L and the other consisting of the vertices of R. As in figure 2, the size of min cut is 1, and C = {(A,B)}. If we don't select (A,B) for contraction, we can get the min cut.

Lemma 2—If G is a multigraph with p vertices and whose min cut has size k, then G has at least pk/2 edges.

Proof

◀ Prev · Parts · Full · Next ▶